package 面试经典150题.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/7/4 21:37
 * @description
 */
public class T17电话号码的字母组合 {
    class Solution {
        List<String> result = new ArrayList<>();
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder temp = new StringBuilder();

        public List<String> letterCombinations(String digits) {
            if (digits.length() == 0 || digits == null) {
                return result;
            }
            backTracking(digits, 0);
            return result;
        }

        private void backTracking(String digits, int index) {
            //如果index的值和digits一样就说明叶子节点里面的结果就是满足我们要求的，
            //而且这里用index来表示我们正在遍历第几个集合，如果digits是23，那么就表示有两个集合
            if (digits.length() == index) {
                result.add(temp.toString());
                return;
            }
            //遍历全部一次记录一次得到的字符串
            String str = numString[digits.charAt(index) - '0'];
            for (int i = 0; i < str.length(); i++) {
                temp.append(str.charAt(i));
                backTracking(digits, index + 1);
                //把拼接的字符串的最后一个字符给删除掉
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }

}
